import heapq


class Tree:
    def __init__(self, n):
        self.n = n
        self.smallK = []
        self.largeK = []
        self.hash1 = set()

    def put(self, val):
        maxNum = -1
        if len(self.largeK):
            maxNum = self.largeK[0] * -1
        if val in self.hash1:
            return True
        if val >= maxNum:
            if len(self.largeK) == self.n:
                return False
        heapq.heappush(self.largeK, val * -1)
        heapq.heappush(self.smallK, val)
        self.hash1.add(val)

        if len(self.largeK) > self.n:
            heapq.heappop(self.largeK)

        return True

    def pop(self):
        val = heapq.heappop(self.smallK)
        return val, len(self.largeK) == self.n and val == self.largeK[0] * -1


class Solution:
    def nthSuperUglyNumber(self, n: int, primes) -> int:
        tree = Tree(n)
        tree.put(1)
        minVal, status = tree.pop()
        while not status:
            for j in primes:
                if not tree.put(minVal * j):
                    break
            minVal, status = tree.pop()
        return minVal


if __name__ == '__main__':
    so = Solution()
    # n = 1000000
    # primes = [7, 19, 29, 37, 41, 47, 53, 59, 61, 79, 83, 89, 101, 103, 109, 127, 131, 137, 139, 157, 167, 179, 181, 199,
    #           211, 229, 233, 239, 241, 251]
    # n = 42
    # primes = [37,53,257]
    n = 800
    primes = [37,43,59,61,67,71,79,83,89,97,101,103,113,127,131,157,163,167,173,179,191,193,197,199,211,229,233,239,251,257]
    # r = so.nthSuperUglyNumber(n, primes)
    # print(r)
    from S313 import Tree as OldTree

    oldTree = OldTree()
    minVal = 1
    tree = Tree(n)
    tree.put(1)
    minVal, status = tree.pop()
    while not status:
        tmp = minVal
        for j in primes:
            if tmp == 257:
                print("###:" + str(j) + "\t" + str(tmp * j) + "\t最大值：{}\t集合数量：{}".format(tree.largeK[0]*-1, len(tree.largeK)))
            if not tree.put(tmp * j):
                break
        minVal, status = tree.pop()

        for j in primes:
            oldTree.put(tmp * j)
            # if 66049 == tmp*j:
            #     print(tmp, j,0)
            #     exit(0)
        minVal2 = oldTree.pop()
        print(minVal, minVal2)
        if minVal!=minVal2:

            break